A Restricted Wolfe Dual for Convex Quadratic Programming

It has long been established that a linear program (LP) has a precise dual form, which is another LP, enabling the derivation of a perfect duality theory. However, the situation is more complex for convex quadratic programming (QP) when the Hessian of the quadratic objective function is neither zero nor positive definite. In 1961, Philip Wolfe introduced a dual form, known as the Wolfe dual problem, for nonlinear programming. For a convex QP, the Wolfe dual problem is another convex QP whose solution set, if nonempty, is always unbounded unless the Hessian of the quadratic objective function is positive definite. This presents significant challenges in designing efficient algorithms for solving large-scale convex QPs. In 2018, together with Xudong Li and Kim Chuan Toh, we successfully addressed this issue by introducing a restricted Wolfe dual form for convex composite QPs. This restricted Wolfe dual eliminates the ambiguity caused by the rank deficiency of the Hessian of the objective function. It possesses many desirable theoretical properties that resemble those of linear conic programming and facilitates the design of efficient dual-based methods, such as the augmented Lagrangian methods, with guaranteed convergence, for solving convex composite QPs. See “my talk slides on the Restricted Wolfe Dual and the Symmetric Gauss-Seidel Decomposition Theorem”.